#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 2e5 + 5;
const int MOD = 1e6 + 3;

int n, k;
int dp[1 << 15];
int cmb[16][16];
string str[15];
void init_cmb() {
  cmb[0][0] = 1;
  rep(i, 1, 15) rep(j, 0, i) {
    cmb[i][j] = (cmb[i - 1][j] + cmb[i - 1][j - 1]) % MOD;
  }
}
bool merge(string& s, string t) {
  int len = s.size();
  rep(i, 0, len - 1) {
    if (t[i] == '?' || s[i] == t[i])
      continue;
    else if (s[i] == '?')
      s[i] = t[i];
    else
      return false;
  }
  return true;
}
ll count(int x) {
  int len = str[0].size();
  string t(len, '?');
  rep(i, 0, n - 1) {
    if (!(x & (1 << i))) continue;
    if (!merge(t, str[i])) return 0;
  }
  ll res = 1;
  for (char c : t) {
    if (c == '?') res = res * 26 % MOD;
  }
  return res;
}
ll solve() {
  if (k > n) return 0;
  ll res = 0;
  int mx = (1 << n) - 1;
  rep(i, 1, mx) {
    int bits = __builtin_popcount(i);
    if (bits < k) continue;
    ll now = count(i);
    if ((bits - k) & 1) {
      res = (res - cmb[bits][k] * now % MOD) % MOD;
    } else {
      res = (res + cmb[bits][k] * now % MOD) % MOD;
    }
  }
  if (res < 0) res += MOD;
  return res;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  init_cmb();
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    rep(i, 0, n - 1) cin >> str[i];
    ll ans = solve();
    cout << ans << endl;
  }
  return 0;
}